/**
 * @Author ZhangCuirong
 * @Date 2025/9/18 13:49
 * @description: 通过观察可以发现，前序遍历该字典树即可得到字典序从小到大的数字序列，遍历到第 k 个节点即为第 k 小的数字。我们可以构造字典树，并通过前序遍历求得目标节点，时间复杂度为 O(k)。实际不需要构造字典树，已知节点 i 的子节点为 (10 × i,10 × i + 1,⋯,10 × i + 9)，可以通过计算找到前序遍历第 k 个节点即可。设当前的字典树的第 i 小的节点为 ni ，则只需按照先序遍历再继续往后找 k−i 个节点即为目标节点。设与 ni 右侧相邻的兄弟节点为 ni+1 ，按照先序遍历的顺序，先访问 ni 构造的子树，再访问 ni+1 ，此时满足 ni < ni+1 。设以 ni 为根节点构成的子树的节点数目为 step(ni) ，则此时有以下两种可能：
 * <p>
 * 如果满足 step(ni) ≤ k−i，则此时可以肯定第 k 小的节点一定不在 ni为根的子树中，存在于 ni的兄弟节点构成的子树中，则此时可以跳过 step(ni) 个节点，从兄弟节点 ni+1 开始往后查找 k − i − step(ni) 个节点。
 * 如果满足 step(ni) > k−i，则此时可以肯定第 k 小的节点一定在 ni构成的子树中，则此时需要在 ni的孩子节点中依次进行查找。此时跳过子树中最小的根节点 ni ，从左侧第一个孩子开始往后查找 k − i − 1 个节点，此时左侧第一个孩子的值为 10 × ni。
 * 依次重复上述操作直到找到 k 小的节点即可。
 * 在这里比较难以处理的是如何计算 step(ni) ，即找到以 ni 为根的子树下有多少节点。可以按照层次遍历子树，firsti 指向第 i 层的最左侧的孩子节点， lasti 指向第 i 层的最右侧的孩子节点，根据推理可以知道: firsti = 10 × firsti − 1 ，lasti = 10 × lasti − 1 + 9 ，第 i 层共有 lasti − firsti + 1 个节点，由于所有的节点都需要满足小于等于 n ，所以第 i 层的最右侧节点应该为 min(n,lasti) ，不断迭代直到 firsti > n 则终止向下搜索。实际上可以观察到最终结果一定是沿着字典树从根节点到某个叶子节点的路径进行搜索。
 */
public class Solution440 {
    /**
     * 查找字典序第k小的数字
     * @param n 范围上限（1到n的数字）
     * @param k 目标位置（1-based索引）
     * @return 第k小的数字
     */
    public int findKthNumber(int n, int k) {
        // 从字典序最小的数字1开始
        int current = 1;
        // 将k转换为0-based索引，方便计算剩余步数
        k--;

        // 当还有剩余位置需要查找时
        while (k > 0) {
            // 计算以current为根的子树包含的节点总数
            int steps = getSteps(current, n);

            // 如果当前子树的节点数小于等于剩余步数，说明目标不在当前子树
            if (steps <= k) {
                // 跳过当前子树所有节点
                k -= steps;
                // 移动到下一个兄弟节点
                current++;
            } else {
                // 目标在当前子树中，需要深入下一层
                // 进入左子节点（current*10）
                current *= 10;
                // 减去当前节点本身
                k--;
            }
        }

        return current;
    }

    /**
     * 计算以current为根的子树中，所有节点值≤n的节点总数
     * @param current 子树根节点
     * @param n 范围上限
     * @return 子树中有效节点的数量
     */
    public int getSteps(int current, long n) {
        int steps = 0;
        // 记录当前层的第一个节点（左边界）
        long first = current;
        // 记录当前层的最后一个节点（右边界）
        long last = current;

        // 当当前层的左边界不超过n时，继续计算
        while (first <= n) {
            // 本层实际有效的节点数：取右边界与n的较小值，减去左边界再加1
            steps += Math.min(last, n) - first + 1;

            // 计算下一层的左边界（当前左边界×10）
            first = first * 10;
            // 计算下一层的右边界（当前右边界×10 + 9）
            last = last * 10 + 9;
        }

        return steps;
    }

    public static void main(String[] args) {
        Solution440 solution = new Solution440();
        // 测试用例1：1-13按字典序排列为[1,10,11,12,13,2,3,4,5,6,7,8,9]，第2个是10
        System.out.println(solution.findKthNumber(13, 2)); // 预期输出：10
        // 测试用例2：只有数字1，第1个是1
        System.out.println(solution.findKthNumber(1, 1));  // 预期输出：1
        // 测试用例3：大数据量测试，验证算法效率
        System.out.println(solution.findKthNumber(1000000000, 1000000000)); // 预期输出：999999999
    }
}
